//最小高度树

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) 
    {
        return helper(nums,0,nums.size()-1);
    }
    TreeNode* helper(vector<int>&nums,int left,int right)
    {
        if(left>right) return nullptr;
        int mid=(left+right)/2;
        TreeNode* newnode=new TreeNode(nums[mid]);
        newnode->left=helper(nums,left,mid-1);
        newnode->right=helper(nums,mid+1,right);
        return newnode;
    }
};

//特定深度节点链表
class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) 
    {
        vector<ListNode*> res;
        if(!tree) return res;
        queue<TreeNode*>q;
        q.push(tree);
        while(!q.empty())
        {
            int size=q.size();
            ListNode * head=new ListNode(-1);
            ListNode* cur=head;
            while(size--)
            {
                TreeNode* front=q.front();
                cur->next=new ListNode(front->val);
                cur=cur->next;
                if(front->left) q.push(front->left);
                if(front->right) q.push(front->right);
                q.pop();
            }
            res.push_back(head->next);
        }
        return res;
    }
};

//检查平衡性
class Solution {
public:
    bool isBalanced(TreeNode* root) 
    {
        if(!root) return true;
        int left=getchildnum(root->left);
        int right=getchildnum(root->right);
        return abs(left-right)<2 && isBalanced(root->left)
            && isBalanced(root->right);
    }
    int getchildnum(TreeNode* root)
    {
        if(!root) return 0;
        return 1+max(getchildnum(root->left),getchildnum(root->right));
    }
};

//合法二叉搜索树
class Solution {
public:
    bool isValidBST(TreeNode* root) 
    {
        stack<TreeNode*>st;
        TreeNode* cur=root;
        long long pre=(long long)INT_MIN-1;
        while(!st.empty() || cur)
        {
            while(cur)
            {
                st.push(cur);
                cur=cur->left;
            }
            //cur为空了 他的父节点是st.top()
            TreeNode* parent=st.top();
            st.pop();
            if(pre >= parent->val) return false;
            pre=parent->val;
            cur=parent->right;
        }
        return true;
    }
};
// 首个共同祖先
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        //后序遍历判断左右子树中有没有p || q 
        if(root==nullptr) return nullptr;
        if(root==p) return p;
        if(root==q) return q;

        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);

        //如果当前节点的左右子树各含p || q那么当前节点就是最近公共祖先
        if(left && right) return root;
        //否则哪个不为空 返回哪个 交给父节点进行判断
        if(left) return left;
        else if(right) return right;
        else return nullptr;

    }
};
//插入
class Solution {
public:
    int insertBits(int N, int M, int i, int j) 
    {
        for(int k=i;k<=j;k++)
        {
            N &=~(1<<k);
        }
        M<<=i;
        return M|N;
    }
};